package com.sx.sx1.lintcode.day717;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LC401 {

    static class Solution {
        /**
         * @param matrix: a matrix of integers
         * @param k:      An integer
         * @return: the kth smallest number in the matrix
         */
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int m = matrix[0].length;
            boolean[][] visited = new boolean[n][m];

            PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
                @Override
                public int compare(Node a, Node b) {
                    return matrix[a.x][a.y]-matrix[b.x][b.y];
                }
            });

            Node root = new Node(0,0,matrix[0][0]);
            visited[0][0]= true;
            pq.add(root);

            for (int i = 0; i <k-1 ; i++) {
                Node cur = pq.poll();
                int x = cur.x;
                int y = cur.y;
                if(x<n && y+1<m && !visited[x][y+1]){
                    visited[x][y+1] = true;
                    Node nnode = new Node(x,y+1,matrix[x][y+1]);
                    pq.add(nnode);
                }

                if(x+1<n && y<m && !visited[x+1][y]){
                    visited[x+1][y]= true;
                    Node nnode = new Node(x+1,y,matrix[x+1][y]);
                    pq.add(nnode);
                }
            }

            return pq.poll().data;
        }

        static class Node {
            public int x;
            public int y;
            public int data;

            public Node(int x1, int y1, int d1) {
                x = x1;
                y = y1;
                data = d1;
            }
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {1, 5, 7},
                {3, 7, 8},
                {4, 8, 9}
        };

        Solution obj = new Solution();
        System.out.println(obj.kthSmallest(arr, 4));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
401 · 排序矩阵中的从小到大第k个数
算法
中等
通过率
34%

题目
题解27
笔记
讨论99+
排名
记录
描述
在一个排序矩阵中找从小到大的第 k 个整数。

排序矩阵的定义为：每一行递增，每一列也递增。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入:
[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]
k = 4
输出: 5
样例 2:

输入:
[
  [1, 2],
  [3, 4]
]
k = 3
输出: 3
挑战
时间复杂度 O(klogn), n 是矩阵的宽度和高度的最大值

标签
企业
Google
Amazon
相关题目

465
两个排序数组和的第K小
困难

791
合并数字
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
388/3325
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
